package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * 1457. 二叉树中的伪回文路径
 *
 * @Author liw
 * @Date 2021/6/14 21:56
 * @Version 1.0
 */
public class PseudoPalindromicPaths {

    public static void main(String[] args) {
        PseudoPalindromicPaths test = new PseudoPalindromicPaths();
        // [2,3,1,3,1,null,1]
        int i = test.pseudoPalindromicPaths(TreeNode.getInstance6());
        System.out.println(i);
    }

    private int[] arr = new int[10];
    private int count = 0;

    public int pseudoPalindromicPaths(TreeNode root) {
        find(root);
        return count;
    }

    private void find(TreeNode node) {
        arr[node.val] += 1;
        if (node.left == null && node.right == null) {
            boolean flag = false;
            for (int i = 1; i <= 9; i++) {
                if ((arr[i] & 1) != 0) {
                    if (flag) {
                        arr[node.val] -= 1;
                        return;
                    }
                    flag = true;
                }
            }
            count++;
            arr[node.val] -= 1;
            return;
        }
        if (node.left != null) {
            find(node.left);
        }
        if (node.right != null) {
            find(node.right);
        }
        arr[node.val] -= 1;
    }

}
